﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class _101SymmetricTree
    {
        public bool IsSymmetric(TreeNode root)
        {
            return IsSame(root.right,root.left);
        }


        public bool IsSame(TreeNode t1,TreeNode t2)
        {
            if (t1 == null && t2 == null)
                return true;

            if (t1 == null || t2 == null)
                return false;


            if (t1.val == t2.val)
                return IsSame(t1.left, t2.right) && IsSame(t1.right, t2.left);
            else
                return false;
        }

        public bool IsSymmetric2(TreeNode root)
        {
            TreeNode t1, t2;

            Queue<TreeNode> _Q = new Queue<TreeNode>();
            _Q.Enqueue(root);
            _Q.Enqueue(root);

            while (_Q.Count != 0)
            {
                t1 = _Q.Dequeue();
                t2 = _Q.Dequeue();

                if (t1 == null && t2 == null)
                    continue;
                if (t1 == null || t2 == null)
                    return false;
                if (t1.val != t2.val)
                    return false;

                _Q.Enqueue(t1.left);
                _Q.Enqueue(t2.right);
                _Q.Enqueue(t1.right);
                _Q.Enqueue(t2.left);
            }
            return true;
        }




        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }
    }
}
